package rbtree;

import avltree.AVLTreeImpl;
import bst.BSTNode;
import rbtree.RBNode.Color;

/**
 * Projeto : Arvore Preta e Vermelha
 * 
 * Equipe:
 * 			Antonio Eduardo
 * 			Gabriel de Brito
 * 			Gervasio Costa
 * 			Jordan Ferreira
 * 			Wesley Breno
 * 
 */

public class RBTreeImpl<T extends Comparable<T>> extends AVLTreeImpl<T>
		implements RBTree<T> {

	private RBNode<T> NIL; // node vazio, para uso em comparacoes

	public RBTreeImpl() {
		root = new RBNode<T>();
		NIL = new RBNode<T>();
	}

	protected boolean verifyProperties() {
		return verifyBlackRoot() && verifyBlackNILs() && verifyNodeColor()
				&& verifyRedChildren() && verifyBlackHeight();
	}

	protected boolean verifyBlackRoot() {
		return ((RBNode<T>) root).getColor() == Color.BLACK;
	}

	protected boolean verifyBlackNILs() {
		return verifyNILs((RBNode<T>) root);
	}

	private boolean verifyNILs(RBNode<T> node) {
		if (!node.isEmpty())
			return verifyNILs((RBNode<T>) node.getLeft())
					&& verifyNILs((RBNode<T>) node.getRight());
		return node.getColor() == Color.BLACK;
	}

	protected boolean verifyNodeColor() {
		return verifyNodeColor((RBNode<T>) root);
	}

	private boolean verifyNodeColor(RBNode<T> node) {
		if (node.isEmpty())
			return true;
		else if (node.getColor() == Color.BLACK || node.getColor() == Color.RED)
			return verifyNodeColor((RBNode<T>) node.getLeft())
					&& verifyNodeColor((RBNode<T>) node.getRight());
		return false;
	}

	protected boolean verifyRedChildren() {
		return verifyRedNode((RBNode<T>) root);
	}

	private boolean verifyRedNode(RBNode<T> node) {
		boolean resp = true;
		if (!node.isEmpty()) {
			if (node.getColor() == Color.RED)
				resp = ((RBNode<T>) node.getLeft()).color == Color.BLACK
						&& ((RBNode<T>) node.getRight()).color == Color.BLACK;
			resp = resp && verifyRedNode((RBNode<T>) node.getLeft())
					&& verifyRedNode((RBNode<T>) node.getRight());
		}
		return resp;
	}

	protected boolean verifyBlackHeight() {
		return blackHeight((RBNode<T>) root.getLeft()) == blackHeight((RBNode<T>) root
				.getRight());
	}

	protected int blackHeight(RBNode<T> node) {
		if (!node.isEmpty())
			if (((RBNode<T>) node.getLeft()).getColor() == Color.BLACK
					|| ((RBNode<T>) node.getRight()).getColor() == Color.BLACK)
				return blackHeight((RBNode<T>) node.getLeft()) + 1;
			else
				return 1;
		return 0;
	}

	@Override
	public void insert(T element) {
		if (!search(element).equals(NIL))
			return;
		RBNode<T> node = new RBNode<T>();
		node.setData(element);
		node.setLeft(NIL);
		node.setRight(NIL);
		node.color = Color.RED;
		insertElement((RBNode<T>) root, node);
		if (!verifyProperties())
			fixUpCase1(search(element));
	}

	private void insertElement(RBNode<T> node, RBNode<T> newNode) {
		RBNode<T> no = node;
		RBNode<T> nodeAux = new RBNode<T>();
		if (search(newNode.getData()).equals(NIL)) {
			while (!no.isEmpty()) {
				nodeAux = no;
				if (newNode.getData().compareTo(no.getData()) > 0)
					no = (RBNode<T>) no.getRight();
				else
					no = (RBNode<T>) no.getLeft();
			}
		}
		newNode.setParent(nodeAux);
		if (nodeAux.isEmpty()) {
			root = newNode;
		} else {
			if (newNode.getData().compareTo(nodeAux.getData()) > 0) {
				nodeAux.setRight(newNode);
			} else {
				nodeAux.setLeft(newNode);
			}
		}
	}
	
	protected void especialRotationLeft(RBNode<T> node) {
		RBNode<T> aux1 = (RBNode<T>) node.getParent();
		RBNode<T> aux2 = (RBNode<T>) node.getLeft();
		node.setParent(node.getAvo());
		node.setLeft(aux1);
		aux1.setParent(node);
		aux1.setRight(aux2);
		aux1.setLeft(NIL);
		aux2.setParent(aux1);
		if (aux1.equals(getRoot())) {
			root = node;
		}
	}

	protected void especialRotationRight(RBNode<T> node) {
		RBNode<T> aux1 = (RBNode<T>) node.getParent();
		RBNode<T> aux2 = (RBNode<T>) node.getRight();
		node.setParent(node.getAvo());
		node.setRight(aux1);
		aux1.setParent(node);
		aux1.setLeft(aux2);
		aux1.setRight(NIL);
		aux2.setParent(aux1);
		if (aux1.equals(getRoot())) {
			root = node;
		}
	}

	private void fixUpCase1(RBNode<T> node) {
		if (node.equals(root)) {
			node.color = Color.BLACK;
		} else {
			fixUpCase2(node);
		}
	}

	private void fixUpCase2(RBNode<T> node) {
		if (!(((RBNode<T>) node.getParent()).getColor() == Color.BLACK)) {
			fixUpCase3(node);
		}
	}

	private void fixUpCase3(RBNode<T> node) {
		if (node.getUncle().getColor() == Color.RED) {
			((RBNode<T>) node.getParent()).setColor();
			node.getUncle().setColor();
			((RBNode<T>) node.getParent().getParent()).setColor();
			fixUpCase1((RBNode<T>) node.getParent().getParent());
		} else {
			fixUpCase4(node);
		}
	}

	private void fixUpCase4(RBNode<T> node) {
		RBNode<T> nodeAux = node;
		if (node.getParent().getRight().equals(node)
				&& node.getParent().getParent().getLeft()
						.equals(node.getParent())) {
			leftRotation((RBNode<T>) node.getParent());
			nodeAux = (RBNode<T>) node.getLeft();
		} else if (node.getParent().getLeft().equals(node)
				&& node.getParent().getParent().getRight()
						.equals(node.getParent())) {
			rightRotation((RBNode<T>) node.getParent());
			nodeAux = (RBNode<T>) node.getRight();
		}

		fixUpCase5(nodeAux);
	}

	private void fixUpCase5(RBNode<T> node) {
		((RBNode<T>) node.getParent()).setColor();
		((RBNode<T>) node.getParent().getParent()).setColor();
		if (node.getParent().getLeft().equals(node)) { // Se node for filho a
														// esquerda
			rightRotation((BSTNode<T>) node.getParent().getParent());
		} else { // cc
			leftRotation((BSTNode<T>) node.getParent().getParent());
		}
	}

	@Override
	public RBNode<T> search(T element) {
		return (RBNode<T>) super.search(element);
	}

	@Override
	public void remove(T element) {
		remove(root, element);
	}

	private void remove(BSTNode<T> node, T element) {
		if (!search(element).equals(NIL)) {
			RBNode<T> deletar = search(element);
			RBNode<T> nodeAux = null;
			RBNode<T> nodeAux2 = null;
			if (!node.equals(NIL)) {
				if (deletar.getLeft().isEmpty() && deletar.getRight().isEmpty()) {
					nodeAux = deletar;
					deletar.setData(null);
					if (deletar.getColor() == Color.BLACK) {
						removeFixUp(deletar);
					}
					if (deletar.isLeaf()) {
						deletar.color = Color.BLACK;
					}
				} else {
					if (deletar.getData().compareTo(maximum().getData()) == 0) {
						nodeAux = deletar;
					} else {
						nodeAux = (RBNode<T>) sucessor(deletar);
					}
					removeFixUp(nodeAux);

					if (!nodeAux.getLeft().isEmpty()) {
						nodeAux2 = (RBNode<T>) nodeAux.getLeft();
					} else {
						nodeAux2 = (RBNode<T>) nodeAux.getRight();
					}
					if (!nodeAux2.isEmpty()) {
						nodeAux2.setParent(nodeAux.getParent());
					}
					if (nodeAux.getParent().isEmpty()) {
						node = nodeAux2;
					} else if (nodeAux.equals(nodeAux.getParent().getLeft())) {
						nodeAux.getParent().setLeft(nodeAux2);

					} else {
						nodeAux.getParent().setRight(nodeAux2);
					}
					if (!nodeAux.equals(deletar)) {
						deletar.setData(nodeAux.getData());
						if (!nodeAux.getLeft().isEmpty()) {
							deletar.setLeft(nodeAux.getLeft());
						}
						if (!nodeAux.getRight().isEmpty()) {
							deletar.setRight(nodeAux.getRight());
						}
					}
				}
			}
		}
	}

	protected void removeFixUp(RBNode<T> node) {
		while (!node.equals(root) && node.getColor() == Color.BLACK) {
			if (node.equals(node.getParent().getLeft())) {// Se for left
				RBNode<T> nodeAux = (RBNode<T>) node.getParent().getRight();
				if (nodeAux.getColor() == Color.RED) {// caso 1 - left
					nodeAux.color = Color.BLACK;
					((RBNode<T>) node.getParent()).color = Color.RED;
					especialRotationLeft(nodeAux);
					nodeAux = (RBNode<T>) node.getParent().getRight();
				}
				if (((RBNode<T>) nodeAux.getLeft()).getColor() == Color.BLACK
						&& ((RBNode<T>) nodeAux.getRight()).getColor() == Color.BLACK) { // 2
																							// caso-left
					nodeAux.color = Color.RED;
					node = (RBNode<T>) node.getParent();
				} else {
					if (((RBNode<T>) nodeAux.getRight()).getColor() == Color.BLACK) {// 3
																						// caso-left
						((RBNode<T>) nodeAux.getLeft()).color = Color.BLACK;
						nodeAux.color = Color.RED;
						miniRotationRigthLeft((BSTNode<T>) nodeAux.getParent());
						nodeAux = (RBNode<T>) node.getParent().getRight();
					}
					if (((RBNode<T>) node.getParent()).color == Color.BLACK) {
						nodeAux.color = Color.BLACK;
					} else {
						nodeAux.color = Color.RED;
					}
					if (!node.isEmpty())
						((RBNode<T>) node.getParent()).color = Color.BLACK;
					if (!nodeAux.isEmpty())
						((RBNode<T>) nodeAux.getRight()).color = Color.BLACK;
					leftRotation((BSTNode<T>) node.getParent());
					node = (RBNode<T>) root;
				}
			}

			else {
				// AKi e o caso Right
				if (node.equals(node.getParent().getRight())) {// Se for left
					RBNode<T> nodeAux = (RBNode<T>) node.getParent().getLeft();
					if (nodeAux.getColor() == Color.RED) {// caso 1 - left
						nodeAux.color = Color.BLACK;
						((RBNode<T>) node.getParent()).color = Color.RED;
						especialRotationRight(nodeAux);
						nodeAux = (RBNode<T>) node.getParent().getLeft();
					}

					if (((RBNode<T>) nodeAux.getLeft()).getColor() == Color.BLACK
							&& ((RBNode<T>) nodeAux.getRight()).getColor() == Color.BLACK) {// 2
																							// caso-left
						nodeAux.color = Color.RED;
						node = (RBNode<T>) node.getParent();
					}

					else {
						if (((RBNode<T>) nodeAux.getLeft()).getColor() == Color.BLACK) {// 3
																						// caso-left
							((RBNode<T>) nodeAux.getLeft()).color = Color.BLACK;
							nodeAux.color = Color.RED;
							miniRotationLeftRigth((BSTNode<T>) nodeAux
									.getParent());
							nodeAux = (RBNode<T>) node.getParent().getLeft();
						}
						if (((RBNode<T>) node.getParent()).color == Color.BLACK) {
							nodeAux.color = Color.BLACK;
						} else {
							nodeAux.color = Color.RED;
						}// 4 caso-left
						if (!node.isEmpty())
							((RBNode<T>) node.getParent()).color = Color.BLACK;
						if (!nodeAux.isEmpty())
							((RBNode<T>) nodeAux.getLeft()).color = Color.BLACK;
						rightRotation((BSTNode<T>) node.getParent());
						node = (RBNode<T>) root;
					}
				}
			}

		}
		node.color = Color.BLACK;
	}
}
